COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂08-Nov-86  1836	JJW  	Qlisp questions (long message)    
C00016 00003	∂10-Nov-86  2226	JJW  	Qlisp questions (continued)  
C00020 ENDMK
C⊗;
∂08-Nov-86  1836	JJW  	Qlisp questions (long message)    
To:   QLISP@SAIL.STANFORD.EDU    
At our meeting this past Friday we decided to look at the definition of
Qlisp to see if we should add or change anything, and to come up with a
more well-defined semantics for the language.

I'd like to begin with a summary of Qlisp as I understand it, along with
some questions that come up or points that aren't clear to me.  Let's
start with a question:

Question 1: Is Qlisp based on Common Lisp, or Scheme, or neither (i.e.,
whatever we want it to be)?  If Common Lisp, do we strictly adhere to
the separate value and function namespaces?  (The Qlisp paper by JMC and
RPG is ambiguous in this regard.)

Qlisp adds the following primitives to the base language: QLET, QLAMBDA,
QCATCH, SUSPEND-PROCESS and RESUME-PROCESS; and changes the definitions
of CATCH, THROW and UNWIND-PROTECT.  It also implicitly changes several
features of the base language.  The Qlisp paper suggests that other new
primitive forms may be defined if there is a need for them.

QLET is like ordinary LET, except that it can spawn processes to compute
values in parallel.  The general form (QLET pred (bindings) body) first
evaluates PRED, and then there are three cases:

(a) The value of PRED is NIL.  QLET then behaves like LET, doing the
    bindings sequentially and executing the body.  (The base language
    determines whether the bindings must be evaluated left-to-right, or
    in an arbitrary order.  Any use of QLET with a predicate that might
    not be NIL would, of course, be stupid to depend on such an order.)

(b) The value of PRED is neither NIL nor EAGER.  QLET spawns a new
    process for each of the bindings and waits for all of these
    processes to finish.  (An implementation could save one process
    creation by letting the parent process handle the last of the
    bindings.)  It then proceeds to evaluate the body.

(c) The value of PRED is EAGER.  QLET spawns a new process for each of
    the bindings, and proceeds to evaluate the body with the variables
    bound to placeholders for the values being computed by these
    processes.  (These are "futures" in Multilisp terminology, and this
    term will be used from here on.)  The evaluation may proceed until
    the body requires one of the values, or the body may terminate
    without requiring any of the values.

    Examples of forms that require values: predicates, conditionals,
    arithmetic, accessor functions (car, cdr, etc.).  Examples of forms
    that don't require values: function application, variable binding,
    assignment, constructors (cons, etc.).

Question 2: Can we be more exact about this?  It seems that for every
primitive operation in the base language we will have to state which
arguments are required and which are not.

    If a value is required, then if the process computing it has
    finished and stored the value in the future, the evaluation of the
    body can proceed without delay.  If the process has not completed,
    the process computing the body must wait until it completes.  It may
    then proceed, possibly waiting again if it needs another value that
    has not been determined.

    The value of the last form in the body is returned as the value of
    the QLET form.  Processes created by the QLET may still be running
    if their values were not required to evaluate the body.  Their
    values may have been ignored entirely, or may have been used in
    forms that don't require values.  For example, the QLET could return
    a cons-cell containing futures for values still being determined, or
    in the simplest case could return a future itself [e.g.,
    (qlet 'eager ((v (foo))) v)].  Therefore we continue running such
    processes even after exiting the QLET.  It is then possible that any
    process may encounter an undetermined future and have to wait, and
    that more than one process may be waiting on the same future.

QLAMBDA introduces a new object called a "process closure".  A process
closure is similar to an ordinary closure in that it returns a value
when it is applied to arguments, and maintains an environment, but
differs in that only one application of a process closure is ever
active.  Thus it provides a primitive with which one can define critical
regions and synchronization.

The general form (QLAMBDA pred (variables) body) evaluates PRED, and has
three cases:

(a) The value of PRED is NIL.  QLAMBDA behaves like LAMBDA, returning an
    ordinary closure.

(b) The value of PRED is neither NIL nor EAGER.  QLAMBDA spawns a new
    process, and returns a process closure.  The process closure is a
    Lisp data structure similar to an ordinary closure, but it contains
    a pointer to the new process, which we will call a "QLAMBDA
    process".  We will call any process that applies a process closure
    to a set of arguments a "calling process".  The QLAMBDA process
    waits for a message.  When the calling process applies the process
    closure, it sends the arguments to the QLAMBDA process.  The QLAMBDA
    process computes the body of the QLAMBDA form with the arguments
    bound to the variables, and returns the resulting value.  The
    calling process waits for the value to be returned unless it is
    ignoring the return value.  Applications of the process closure are
    synchronized, so that no two are in progress at the same time.

Question 3: When is a value considered to be ignored?  The only example
given in the Qlisp paper is that a top-level form in an explicit or
implicit PROGN (except the last top-level form, which is the value of
the PROGN), ignores its value.

Question 4: If a process closure is applied in a value-ignoring
position, but the QLAMBDA process is busy, does the calling process wait
until its message has been read by the QLAMBDA process, or does it just
enqueue the message and continue?  Remarks in the Qlisp paper tend to
imply the latter.

(c) The value of PRED is EAGER.  A process closure and an QLAMBDA
    process are created just as above, but the QLAMBDA process
    immediately starts computing the body of the QLAMBDA form.  To do
    this, the variables are bound to futures.  When the process closure
    is applied, the values of the futures are set to the arguments and
    the QLAMBDA process may proceed if it had to wait on one of the
    futures.  If the QLAMBDA process happens to compute its value
    without waiting on any of the futures, it will wait at that point
    until it is called.  In either case, once it returns a value to its
    caller, it again begins to evaluate the QLAMBDA body with a new set
    of futures bound to the variables.

CATCH, QCATCH and THROW provide non-local exits and allow the killing of
processes.  The value returned by (CATCH tag form) or (QCATCH tag form)
is the value of FORM, if no THROW is executed before FORM returns a
value.  CATCH kills any processes still executing when FORM returns,
while QCATCH waits for them to finish.  If (THROW tag value) is
executed, we search upwards through the stack of function calls and the
tree of process creations until we find a CATCH or QCATCH with a
matching tag.  We then kill all processes created as a result of the
CATCH or QCATCH and return the value in the THROW as the value of the
CATCH or QCATCH.

Question 5: There is a third possibility: CATCH could return a value
normally (no THROW was executed), but some processes could still be
computing part of that value, as a result of eager QLETs.  We will want
these processes to continue, but might not want to wait for their
values.  Shouldn't there be a way to exit the CATCH but leave processes
running?  I would argue that ordinary return from a CATCH shouldn't kill
any processes; that THROW should be the only way to kill something.

Question 6: What does it mean to kill a QLAMBDA process?  Since the
process closure still exists and may be applied after we leave the CATCH
or QCATCH, we don't want to prevent the QLAMBDA process from ever
running again.  But if, at the time we kill processes, a QLAMBDA process
is working on computing some value that is no longer needed, we will
want to stop it and unwind it back to the point where it is ready to
accept a new set of arguments.

Question 7: If a THROW occurs inside a QLAMBDA process, and there is no
corresponding CATCH in that process, what is the "parent" process that
we should examine to continue searching for the tag?  Is it the process
that created the process closure?  That one might no longer exist.  Is
it the process currently calling the QLAMBDA process?  That one might be
gone too, if the call was in a value-ignoring position.

(to be continued ...)
If anyone has read this far, I'd be glad to hear your opinions.

∂10-Nov-86  2226	JJW  	Qlisp questions (continued)  
To:   QLISP@SAIL.STANFORD.EDU    
RPG's answer to Question 1 in the previous message is that Qlisp must be
(as promised to DARPA) an extension of full Common Lisp, including the
separate function and value namespaces and all of the other features of
the language.  So that answers that.

Here's a continuation of the descriptions of current Qlisp features along
with some more questions:

UNWIND-PROTECT is used to prevent terminated processes from leaving things
in an undesirable state.  The form (UNWIND-PROTECT form cleanup) evaluates
FORM and guarantees that CLEANUP will be executed whether FORM returns
normally or is terminated by a THROW.

Question 8: The Qlisp paper only discusses the case where a THROW takes
place because of a computation done inside FORM.  Another important case
is when processes containing UNWIND-PROTECT are killed because of a THROW
in another process.  When this happens, do we execute the cleanup code for
all UNWIND-PROTECTs in processes being killed?

SUSPEND-PROCESS and RESUME-PROCESS are used (not surprisingly) to suspend
and resume processes.  They take as an argument a process closure and
suspend or resume the associated process.  SUSPEND-PROCESS can also take
no arguments, in which case it causes a process to suspend itself.

Question 9: What is the effect of SUSPEND-PROCESS to an already suspended
process, or RESUME-PROCESS to a process that is not suspended?

Question 10: How does suspension interact with killing of processes?  If a
suspended process is killed, does it wake up to execute UNWIND-PROTECT
cleanup forms?  Can a process be suspended while it is executing a cleanup
form?  [If the answer to this is no, then (UNWIND-PROTECT NIL (FOO)) will
be a concise way to ensure that (FOO) is executed without possibility of
being killed or suspended.]

Question 11: If a process is not associated with a process closure (i.e.,
it was created by QLET), can we suspend or resume it?